{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "origin_pos": 0
   },
   "source": [
    "# Text Preprocessing\n",
    ":label:`sec_text_preprocessing`\n",
    "\n",
    "We have reviewed and evaluated\n",
    "statistical tools \n",
    "and prediction challenges\n",
    "for sequence data.\n",
    "Such data can take many forms.\n",
    "Specifically,\n",
    "as we will focus on\n",
    "in many chapters of the book,\n",
    "text is one of the most popular examples of sequence data.\n",
    "For example,\n",
    "an article can be simply viewed as a sequence of words, or even a sequence of characters.\n",
    "To facilitate our future experiments\n",
    "with sequence data,\n",
    "we will dedicate this section\n",
    "to explain common preprocessing steps for text.\n",
    "Usually, these steps are:\n",
    "\n",
    "1. Load text as strings into memory.\n",
    "1. Split strings into tokens (e.g., words and characters).\n",
    "1. Build a table of vocabulary to map the split tokens to numerical indices.\n",
    "1. Convert text into sequences of numerical indices so they can be manipulated by models easily.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%load ../utils/djl-imports"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "origin_pos": 4
   },
   "source": [
    "## Reading the Dataset\n",
    "\n",
    "To get started we load text from H. G. Wells' [*The Time Machine*](http://www.gutenberg.org/ebooks/35).\n",
    "This is a fairly small corpus of just over 30000 words, but for the purpose of what we want to illustrate this is just fine.\n",
    "More realistic document collections contain many billions of words.\n",
    "The following function reads the dataset into a list of text lines, where each line is a string.\n",
    "For simplicity, here we ignore punctuation and capitalization.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "public String[] readTimeMachine() throws IOException {\n",
    "    URL url = new URL(\"http://d2l-data.s3-accelerate.amazonaws.com/timemachine.txt\");\n",
    "    String[] lines;\n",
    "    try (BufferedReader in = new BufferedReader(new InputStreamReader(url.openStream()))) {\n",
    "        lines = in.lines().toArray(String[]::new);\n",
    "    }\n",
    "\n",
    "    for (int i = 0; i < lines.length; i++) {\n",
    "        lines[i] = lines[i].replaceAll(\"[^A-Za-z]+\", \" \").strip().toLowerCase();\n",
    "    }\n",
    "    return lines;\n",
    "}\n",
    "\n",
    "String[] lines = readTimeMachine();\n",
    "System.out.println(\"# text lines: \" + lines.length);\n",
    "System.out.println(lines[0]);\n",
    "System.out.println(lines[10]);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "origin_pos": 6
   },
   "source": [
    "## Tokenization\n",
    "\n",
    "The following `tokenize` function\n",
    "takes an array (`lines`) as the input,\n",
    "where each element is a text sequence (e.g., a text line).\n",
    "Each text sequence is split into a list of tokens.\n",
    "A *token* is the basic unit in text.\n",
    "In the end,\n",
    "a list of token lists are returned,\n",
    "where each token is a string.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "public String[][] tokenize(String[] lines, String token) throws Exception {\n",
    "    // Split text lines into word or character tokens.\n",
    "    String[][] output = new String[lines.length][];\n",
    "    if (token == \"word\") {\n",
    "        for (int i = 0; i < output.length; i++) {\n",
    "            output[i] = lines[i].split(\" \");\n",
    "        }\n",
    "    } else if (token == \"char\") {\n",
    "        for (int i = 0; i < output.length; i++) {\n",
    "            output[i] = lines[i].split(\"\");\n",
    "        }\n",
    "    } else {\n",
    "        throw new Exception(\"ERROR: unknown token type: \" + token);\n",
    "    }\n",
    "    return output; \n",
    "}\n",
    "String[][] tokens = tokenize(lines, \"word\");\n",
    "for (int i = 0; i < 11; i++) {\n",
    "    System.out.println(Arrays.toString(tokens[i]));\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "origin_pos": 8
   },
   "source": [
    "## Vocabulary\n",
    "\n",
    "The string type of the token is inconvenient to be used by models, which take numerical inputs.\n",
    "Now let us build a dictionary (HashMap), often called *vocabulary* as well, to map string tokens into numerical indices starting from 0.\n",
    "To do so, we first count the unique tokens in all the documents from the training set,\n",
    "namely a *corpus*,\n",
    "and then assign a numerical index to each unique token according to its frequency.\n",
    "Rarely appeared tokens are often removed to reduce the complexity.\n",
    "Any token that does not exist in the corpus or has been removed is mapped into a special unknown token “&lt;unk&gt;”.\n",
    "We optionally add a list of reserved tokens, such as\n",
    "“&lt;pad&gt;” for padding,\n",
    "“&lt;bos&gt;” to present the beginning for a sequence, and “&lt;eos&gt;” for the end of a sequence.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "public class Vocab {\n",
    "    public int unk;\n",
    "    public List<Map.Entry<String, Integer>> tokenFreqs;\n",
    "    public List<String> idxToToken;\n",
    "    public HashMap<String, Integer> tokenToIdx;\n",
    "\n",
    "    public Vocab(String[][] tokens, int minFreq, String[] reservedTokens) {\n",
    "        // Sort according to frequencies\n",
    "        LinkedHashMap<String, Integer> counter = countCorpus2D(tokens);\n",
    "        this.tokenFreqs = new ArrayList<Map.Entry<String, Integer>>(counter.entrySet()); \n",
    "        Collections.sort(tokenFreqs, \n",
    "            new Comparator<Map.Entry<String, Integer>>() { \n",
    "                public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) { \n",
    "                    return (o2.getValue()).compareTo(o1.getValue()); \n",
    "                }\n",
    "            });\n",
    "        \n",
    "        // The index for the unknown token is 0\n",
    "        this.unk = 0;\n",
    "        List<String> uniqTokens = new ArrayList<>();\n",
    "        uniqTokens.add(\"<unk>\");\n",
    "        Collections.addAll(uniqTokens, reservedTokens);\n",
    "        for (Map.Entry<String, Integer> entry : tokenFreqs) {\n",
    "            if (entry.getValue() >= minFreq && !uniqTokens.contains(entry.getKey())) {\n",
    "                uniqTokens.add(entry.getKey());\n",
    "            }\n",
    "        }\n",
    "        \n",
    "        this.idxToToken = new ArrayList<>();\n",
    "        this.tokenToIdx = new HashMap<>();\n",
    "        for (String token : uniqTokens) {\n",
    "            this.idxToToken.add(token);\n",
    "            this.tokenToIdx.put(token, this.idxToToken.size()-1);\n",
    "        }\n",
    "    }\n",
    "    \n",
    "    public int length() {\n",
    "        return this.idxToToken.size();\n",
    "    }\n",
    "    \n",
    "    public Integer[] getIdxs(String[] tokens) {\n",
    "        List<Integer> idxs = new ArrayList<>();\n",
    "        for (String token : tokens) {\n",
    "            idxs.add(getIdx(token));\n",
    "        }\n",
    "        return idxs.toArray(new Integer[0]);\n",
    "        \n",
    "    }\n",
    "    \n",
    "    public Integer getIdx(String token) {\n",
    "        return this.tokenToIdx.getOrDefault(token, this.unk);\n",
    "    }\n",
    "    \n",
    "    \n",
    "}\n",
    "\n",
    "public LinkedHashMap<String, Integer> countCorpus(String[] tokens) {\n",
    "    /* Count token frequencies. */\n",
    "    LinkedHashMap<String, Integer> counter = new LinkedHashMap<>();\n",
    "    if (tokens.length != 0) {\n",
    "        for (String token : tokens) {\n",
    "            counter.put(token, counter.getOrDefault(token, 0)+1);\n",
    "        }\n",
    "    }\n",
    "    return counter;\n",
    "}\n",
    "\n",
    "public LinkedHashMap<String, Integer> countCorpus2D(String[][] tokens) {\n",
    "    /* Flatten a list of token lists into a list of tokens */\n",
    "    List<String> allTokens = new ArrayList<String>();\n",
    "    for (int i = 0; i < tokens.length; i++) {\n",
    "        for (int j = 0; j < tokens[i].length; j++) {\n",
    "             if (tokens[i][j] != \"\") {\n",
    "                allTokens.add(tokens[i][j]);\n",
    "             }\n",
    "        }\n",
    "    }\n",
    "    return countCorpus(allTokens.toArray(new String[0]));\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "origin_pos": 10
   },
   "source": [
    "We construct a vocabulary using the time machine dataset as the corpus. \n",
    "Then we print the first few frequent tokens with their indices."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "Vocab vocab = new Vocab(tokens, 0, new String[0]);\n",
    "for (int i = 0; i < 10; i++) {\n",
    "    String token = vocab.idxToToken.get(i);\n",
    "    System.out.print(\"(\" + token + \", \" + vocab.tokenToIdx.get(token) + \") \");\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "origin_pos": 12
   },
   "source": [
    "Now we can convert each text line into a list of numerical indices.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "for (int i : new int[] {0,10}) {\n",
    "    System.out.println(\"Words:\" + Arrays.toString(tokens[i]));\n",
    "    System.out.println(\"Indices:\" + Arrays.toString(vocab.getIdxs(tokens[i])));\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "origin_pos": 14
   },
   "source": [
    "## Putting All Things Together\n",
    "\n",
    "Using the above functions, we package everything into the `loadCorpusTimeMachine` function, which returns `corpus`, a list of token indices, and `vocab`, the vocabulary of the time machine corpus.\n",
    "The modifications we did here are:\n",
    "i) we tokenize text into characters, not words, to simplify the training in later sections;\n",
    "ii) `corpus` is a single list, not a list of token lists, since each text line in the time machine dataset is not necessarily a sentence or a paragraph.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "public Pair<List<Integer>, Vocab> loadCorpusTimeMachine(int maxTokens) throws IOException, Exception {\n",
    "    /* Return token indices and the vocabulary of the time machine dataset. */\n",
    "    String[] lines = readTimeMachine();\n",
    "    String[][] tokens = tokenize(lines, \"char\");\n",
    "    Vocab vocab = new Vocab(tokens, 0, new String[0]);\n",
    "    // Since each text line in the time machine dataset is not necessarily a\n",
    "    // sentence or a paragraph, flatten all the text lines into a single list\n",
    "    List<Integer> corpus = new ArrayList<>();\n",
    "    for (int i = 0; i < tokens.length; i++) {\n",
    "        for (int j = 0; j < tokens[i].length; j++) {\n",
    "            if (tokens[i][j] != \"\") {\n",
    "                corpus.add(vocab.getIdx(tokens[i][j]));\n",
    "            }\n",
    "        }\n",
    "    }\n",
    "    if (maxTokens > 0) {\n",
    "        corpus = corpus.subList(0, maxTokens);\n",
    "    }\n",
    "    return new Pair(corpus, vocab);\n",
    "}\n",
    "\n",
    "Pair<List<Integer>, Vocab> corpusVocabPair = loadCorpusTimeMachine(-1);\n",
    "List<Integer> corpus = corpusVocabPair.getKey();\n",
    "Vocab vocab = corpusVocabPair.getValue();\n",
    "\n",
    "System.out.println(corpus.size());\n",
    "System.out.println(vocab.length());"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "origin_pos": 16
   },
   "source": [
    "## Summary\n",
    "\n",
    "* Text is an important form of sequence data.\n",
    "* To preprocess text, we usually split text into tokens, build a vocabulary to map token strings into numerical indices, and convert text data into token indices for  models to manipulate.\n",
    "\n",
    "\n",
    "## Exercises\n",
    "\n",
    "1. Tokenization is a key preprocessing step. It varies for different languages. Try to find another three commonly used methods to tokenize text.\n",
    "1. In the experiment of this section, tokenize text into words and vary the `minFreq` arguments of the `Vocab` instance. How does this affect the vocabulary size?"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Java",
   "language": "java",
   "name": "java"
  },
  "language_info": {
   "codemirror_mode": "java",
   "file_extension": ".jshell",
   "mimetype": "text/x-java-source",
   "name": "Java",
   "pygments_lexer": "java",
   "version": "14.0.2+12"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
